Finding approximately rank-one submatrices with the nuclear norm and l1 norm

摘要

We propose a convex optimization formulation with the nuclear norm and$\ell_1$-norm to find a large approximately rank-one submatrix of a givennonnegative matrix. We develop optimality conditions for the formulation andcharacterize the properties of the optimal solutions. We establish conditionsunder which the optimal solution of the convex formulation has a specificsparse structure. Finally, we show that, under certain hypotheses, with highprobability, the approach can recover the rank-one submatrix even when it iscorrupted with random noise and inserted as a submatrix into a much largerrandom noise matrix.